package com.sheng.leetcode.year2022.swordfingeroffer.day07;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/09/06
 *
 * 剑指 Offer 26. 树的子结构
 *
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 *
 * 例如:
 * 给定的树 A:
 *      3
 *     / \
 *    4   5
 *   / \
 *  1   2
 *
 * 给定的树 B：
 *    4
 *   /
 *  1
 * 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
 *
 * 示例 1：
 * 输入：A = [1,2,3], B = [3,1]
 * 输出：false
 *
 * 示例 2：
 * 输入：A = [3,4,5,1,2], B = [4,1]
 * 输出：true
 *
 * 限制：
 *
 * 0 <= 节点个数 <= 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Sword0026 {

    @Test
    public void test01() {
//        TreeNode A = new TreeNode(1);
//        A.left = new TreeNode(2);
//        A.right = new TreeNode(3);
//        TreeNode B = new TreeNode(3);
//        B.left = new TreeNode(1);

        TreeNode A = new TreeNode(3);
        TreeNode left = new TreeNode(4);
        left.left = new TreeNode(1);
        left.right = new TreeNode(1);
        A.left = left;
        A.right = new TreeNode(5);
        TreeNode B = new TreeNode(4);
        B.left = new TreeNode(1);
        System.out.println(new Solution().isSubStructure(A, B));
    }
}
class Solution {

    boolean flag = false;
    TreeNode t;
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        // 思路，将A的每一个结点都和B进行比较，如果B的所有结点子节点，在A的其中一个结点中都有相同的，则B是A的子结构
        t = B;
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(A);
        if (compare(A, t)) {
            flag = true;
        }
        bfs(nodes);
        return flag;
    }

    public void bfs(List<TreeNode> treeNodes) {
        List<TreeNode> nodes = new ArrayList<>();
        for (TreeNode node : treeNodes) {
            if (node.left != null) {
                nodes.add(node.left);
                if (compare(node.left, t)) {
                    flag = true;
                }
            }
            if (node.right != null) {
                nodes.add(node.right);
                if (compare(node.right, t)) {
                    flag = true;
                }
            }
        }
        if (nodes.size() > 0) {
            bfs(nodes);
        }
    }

    public boolean compare(TreeNode t1, TreeNode t2) {
        if (t2 == null) {
            return true;
        } else if (t1 == null) {
            return false;
        }else if (t1.val == t2.val) {
            if (t1.left == null && t2.left != null) {
                return false;
            } else if (t1.right == null && t2.right != null) {
                return false;
            } else if (t2.left == null && t2.right == null) {
                return true;
            } else {
                return compare(t1.left, t2.left) && compare(t1.right, t2.right);
            }
        }
        return false;
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

//class Solution {
//    public boolean isSubStructure(TreeNode A, TreeNode B) {
//        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
//    }
//    boolean recur(TreeNode A, TreeNode B) {
//        if(B == null) return true;
//        if(A == null || A.val != B.val) return false;
//        return recur(A.left, B.left) && recur(A.right, B.right);
//    }
//}
//
//作者：jyd
//链接：https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
